package com.faiz.algorithm;

public class ReverseLinkedList {

    //递归反转链表
    public static ListNode reverseLikedList(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode last = reverseLikedList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
    private static ListNode successor = null;
    //递归反转链表的前N个节点
    public static ListNode reverseFrontNListNode(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        //使用newHead变量来接收新链表的头
        ListNode newHead = reverseFrontNListNode(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return newHead;
    }
    //递归反转[m, n]区间内的节点
    public static ListNode reverseM2NListNode(ListNode head, int m, int n) {
        if (m == 1) {
            return reverseFrontNListNode(head, n);
        }
        head.next = reverseM2NListNode(head.next, m - 1, n -1);
        return head;
    }

    public static void main(String[] args) {

    }
}
